//给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。 
//
// 示例: 
//
// 输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
//输出:
//[
//  ["ate","eat","tea"],
//  ["nat","tan"],
//  ["bat"]
//] 
//
// 说明： 
//
// 
// 所有输入均为小写字母。 
// 不考虑答案输出的顺序。 
// 
// Related Topics 哈希表 字符串


package leetcode.d_1_99;

import java.util.*;

//Java：字母异位词分组
public class P49GroupAnagrams{
    public static void main(String[] args) {
        P49GroupAnagrams solution = new P49GroupAnagrams();
        List<List<String>> res = solution.groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"});
        System.out.println(res);
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        Map<String, List<String>> groupMap = new HashMap<>();
        for (String str : strs) {
            String code = encode(str);
            groupMap.putIfAbsent(code, new ArrayList<>());
            groupMap.get(code).add(str);
        }
        for (List<String> group : groupMap.values()) {
            res.add(group);
        }
        return res;
    }

    public String encode(String s) {
        char[] result = new char[26];
        char[] chars = s.toCharArray();
        for (char ch : chars) {
            result[ch-'a']++;
        }
        return String.valueOf(result);
    }

    // 取巧的方法
    public List<List<String>> groupAnagrams2(String[] strs) {
        if (strs.length == 0){
            return new ArrayList<>();
        }
        Map<String, List<String >> ans = new HashMap<>();
        for (String str :  strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = String.valueOf(chars);
            if (!ans.containsKey(key)){
                ans.put(key, new ArrayList<>());
            }
            ans.get(key).add(str);
        }
        return new ArrayList<>(ans.values());
    }

}